/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==nullptr || head->next==nullptr || head->next->next==nullptr)
            return; // 处理边界情况
 
        ListNode *fast = head, *slow = head;
        while(fast && fast->next) // 找到中间结点
        {
            slow = slow->next;
            fast = fast->next->next;
        }
 
        ListNode* slowNext = slow->next;
        slow->next = nullptr; // 两个链表断开
        slow = slowNext;
        ListNode *reverseList = nullptr;
        while(slow) // 中间结点后面的头插到翻转链表
        {
            slowNext = slow->next;
            slow->next = reverseList;
            reverseList = slow;
            slow = slowNext;
        }
 
        ListNode* tmp = head; // 合并两个链表
        ListNode *cur1 = head->next, *cur2 = reverseList;
        while(cur1 && cur2)
        {
            tmp->next = cur2;
            tmp = tmp->next;
            cur2 = cur2->next;
 
            tmp->next = cur1;
            cur1 = cur1->next;
            tmp = tmp->next;
        }
    }
};